#include "myTree.h"
#include <iostream>
using namespace std;

void TreeNode::printNode()
{
    cout << this->data;
}

TreeNode::TreeNode(char c, TreeNode* p1, TreeNode* p2, NodeTag t1, NodeTag t2)
{
    data = c;
    leftChild = p1;
    rightChild = p2;
    lTag = t1;
    rTag = t2;
}

TreeNode::TreeNode(TreeNode* p)
{
    if (p != NULL)
    {
        data = p->data;
        leftChild = p->leftChild;
        rightChild = p->rightChild;
        lTag = p->lTag;
        rTag = p->rTag;
    }
}
 
TreeNode::~TreeNode()  {   }




MyTree::MyTree()
{
    TreeNode* root = new TreeNode('^', NULL, NULL, Link, Thread);
}
MyTree::MyTree(const char arr[])
{
    root = new TreeNode('^', NULL, NULL, Link, Link);
    root->leftChild = new TreeNode(arr[0], NULL, NULL, Link, Link);
    root->rightChild = NULL;
    TreeNode* fron = root->leftChild;
    stack <TreeNode*> q;
    int bol = 1;
    for (int i = 1; i < strlen(arr); i++)
    {
        if (bol)
        {
            if (arr[i] == '@')
            {
                fron->leftChild = NULL;
                bol = 0;
            }
            else
            {
                fron->leftChild = new TreeNode(arr[i], NULL, NULL, Link, Link);
                q.push(fron);
                fron = fron->leftChild;
            }
        }
        else
        {
            if (arr[i] == '@')
            {
                fron->rightChild = NULL;
                if (!q.empty())
                {
                    fron = q.top();
                    q.pop();
                }
            }
            else
            {
                fron->rightChild = new TreeNode(arr[i], NULL, NULL, Link, Link);
                q.push(fron->rightChild);
                if (!q.empty())
                {
                    fron = q.top();
                    q.pop();
                }
                bol = 1;
            }
        }
    }

}
MyTree::MyTree(const MyTree& t) 
{
    root = new TreeNode(t.root);
    root->leftChild = new TreeNode(t.root->leftChild);
    if(t.root->rightChild != NULL)
    root->rightChild = new TreeNode(t.root->rightChild);
    queue<TreeNode*> q;
    queue<TreeNode*> q2;

    TreeNode* fron = new TreeNode(t.root->leftChild);
    TreeNode* now = root->leftChild;
    while (!q.empty() || (fron->lTag != Thread  && fron->leftChild != NULL)|| (fron->rTag != Thread && fron->rightChild != NULL))
    {
        if (fron->leftChild != NULL)
            now->leftChild = new TreeNode(fron->leftChild);
        if (fron->rightChild != NULL)
            now->rightChild = new TreeNode(fron->rightChild);
        if (fron->lTag != Thread && fron->leftChild != NULL)
        {
            q.push(fron->leftChild);
            q2.push(now->leftChild);
        }
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            q.push(fron->rightChild);
            q2.push(now->rightChild);
        }
        if (!q.empty())
        {
            fron = q.front();
            now = q2.front();
            q2.pop();
            q.pop();
        }
    }
    if (fron->leftChild != NULL)
        now->leftChild = new TreeNode(fron->leftChild);
    if (fron->rightChild != NULL)
        now->rightChild = new TreeNode(fron->rightChild);
}
MyTree::~MyTree()             
{
    stack <TreeNode*> s; queue<TreeNode*> q;
    TreeNode* fron = root->leftChild;
    while (!q.empty() || (fron->lTag != Thread && fron->leftChild != NULL) || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        if (fron->lTag != Thread && fron->leftChild != NULL)
        {
            q.push(fron->leftChild);
            s.push(fron->leftChild);
        }
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            q.push(fron->rightChild);
            s.push(fron->rightChild);
        }
        if (!q.empty())
        {
            fron = q.front();
            q.pop();
        }
    }
    while (!s.empty())
    {
        TreeNode* t = s.top();
        s.pop();
        delete t;
    }
    delete root;
}

void MyTree::preOrderTraverse()   
{
    stack <TreeNode*> s;
    TreeNode* fron = root->leftChild;
    int t = 0;
    cout << root->leftChild->data;
    while (!s.empty() ||( (fron->lTag != Thread && fron->leftChild != NULL) && !t )|| (fron->rTag != Thread && fron->rightChild != NULL))
    {
       
        if (fron->lTag != Thread && !t && fron->leftChild != NULL)
        {
            s.push(fron);
            fron = fron->leftChild;
        }
        else if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            fron = fron->rightChild;
            t = 0;
        }
        else if(!s.empty())
        {
            fron = s.top();
            s.pop();
            t = 1;
        } 
        if (!t)
        {
            cout << fron->data;
        }

    }


}
void MyTree::inOrderTraverse()    
{
    stack <TreeNode*> s;
    stack <int> sss;
    TreeNode* fron = root->leftChild;
    int t = 0;
    s.push(fron);
    while (!s.empty() || (fron->rTag != Thread && fron->rightChild != NULL) || (fron->leftChild != NULL && fron->lTag != Thread && !t))
    {
        while (fron->lTag != Thread && !t && fron->leftChild != NULL)
        {
            if (fron != root->leftChild)
            {
                s.push(fron);
                sss.push(1);
            }
            fron = fron->leftChild;
        }
        cout << fron->data;
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            fron = fron->rightChild;
            t = 0;
        }
        else if (!s.empty())
        {
            fron = s.top();
            t = 1;
            s.pop();
        }
    }
        cout << fron->data;
}
void MyTree::postOrderTraverse()  
{
    stack <TreeNode*> s;
    stack <int> pos;
    TreeNode* fron = root->leftChild;
    int t = 0, p = 0, u = 0;
    while (!s.empty() || t != 2)
    {
        while (fron->lTag != Thread && fron->leftChild != NULL && t != 2 && t != 1)
        {
            s.push(fron);
            pos.push(1);
            fron = fron->leftChild;
            t = 0;
        }
        if (t == 2)
        {
            cout << fron->data;
            if (!s.empty())
            {
                fron = s.top();
                s.pop();
                t = pos.top();
                pos.pop();
            }
        }
        if (fron->rTag == Thread || fron->rightChild == NULL)
        {
            t = 2;
        }
        else if (fron->rTag != Thread && fron->rightChild != NULL && t != 2)
        {
            s.push(fron);
            pos.push(2);
            fron = fron->rightChild;
            t = 0;
        }
    }
    if (t == 2)
        cout << fron->data;

}
int MyTree::countLeaf()            
{
    int num = 0;
    queue<TreeNode*> q;
    TreeNode* fron = root->leftChild;
    while (!q.empty() || (fron->lTag != Thread && fron->leftChild != NULL) || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        if ((fron->lTag == Thread || fron->leftChild == NULL)&&(fron->rightChild == NULL || fron->rTag == Thread))
            num++;
        if (fron->lTag != Thread && fron->leftChild != NULL)
        {
            q.push(fron->leftChild);
        }
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            q.push(fron->rightChild);
        }
        if (!q.empty())
        {
            fron = q.front();
            q.pop();
        }
    }
    return num + 1;
}
int Depth(TreeNode* fron)
{
    if ((fron->lTag == Thread || fron->leftChild == NULL) && (fron->rightChild == NULL || fron->rTag == Thread))
        return 1;
    if (fron->lTag == Thread || fron->leftChild == NULL)
        return (Depth(fron->rightChild) + 1);
    if (fron->rightChild == NULL || fron->rTag == Thread)
        return (Depth(fron->leftChild) + 1);
    return (max(Depth(fron->rightChild), Depth(fron->leftChild)) + 1);
}
int MyTree::countHeight()          
{
    return Depth(root->leftChild);

}
bool MyTree::isThreadedTree()     
{
    return root->rTag == Thread;
}
bool MyTree::inOrderThreading()    
{
    stack <TreeNode*> s;  
    stack <TreeNode*> h;
    TreeNode* fron = root->leftChild;
    TreeNode* f = root;
    int t = 0;
    s.push(fron);
    while (!s.empty() || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        while (fron->lTag != Thread && !t && fron->leftChild != NULL)
        {
            if (fron != root->leftChild)
                s.push(fron);
            fron = fron->leftChild;
        }
        if (fron->leftChild == NULL)
        {
            fron->leftChild = f;
            fron->lTag = Thread;
        }
        f = fron;
        h.push(fron);
        if (fron->rightChild == NULL)
        {
            if (!h.empty())
            {
                h.top()->rightChild = f;
                h.pop();
            }
            fron->rTag = Thread;
            h.push(fron);
        }
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            fron = fron->rightChild;
            t = 0;
        }
        else if (!s.empty())
        {
            fron = s.top();
            t = 1;
            s.pop();
        }
    }
    fron = root->leftChild;
    while (fron->rightChild != NULL)
    {
        fron = fron->rightChild;
    }
    fron->rightChild = root;
    fron->rTag = Thread;
    root->rightChild = fron;
    root->rTag = Thread;

    return true;
}
TreeNode& MyTree::locateNode(const char& a)  
{
    queue<TreeNode*> q;
    TreeNode *fron = root->leftChild;
    while (!q.empty() || (fron->lTag != Thread && fron->leftChild != NULL) || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        if (fron->data == a)
            return *fron;
        if (fron->lTag != Thread && fron->leftChild != NULL)
        {
            q.push(fron->leftChild);
        }
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            q.push(fron->rightChild);
        }
        if (!q.empty())
        {
            fron = q.front();
            q.pop();
        }
    }
    if (fron->data == a)
        return *fron;
    else
        return *new TreeNode('0', NULL, NULL, Link, Link);
}
TreeNode& MyTree::preNode(const TreeNode& u) 
{
    string z = "";
    stack <TreeNode*> s;
    TreeNode* fron = root->leftChild;
    int t = 0;
    s.push(fron);
    while (!s.empty() || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        while (fron->lTag != Thread && !t && fron->leftChild != NULL)
        {
            if (fron != root->leftChild)
                s.push(fron);
            fron = fron->leftChild;
        }
        z += fron->data;
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            fron = fron->rightChild;
            t = 0;
        }
        else if (!s.empty())
        {
            fron = s.top();
            t = 1;
            s.pop();
        }
    }
    z += fron->data;
    int i = 0;
    for (; i < z.length(); i++)
    {
        if (z[i] == u.data)
            break;
    }
    if (i != 0)
        return locateNode(z[i - 1]);
    else
        return *root->rightChild;
}
TreeNode& MyTree::nextNode(const TreeNode& u)
{
    string z = "";
    stack <TreeNode*> s;
    TreeNode* fron = root->leftChild;
    int t = 0;
    s.push(fron);
    while (!s.empty() || (fron->rTag != Thread && fron->rightChild != NULL))
    {
        while (fron->lTag != Thread && !t && fron->leftChild != NULL)
        {
            if (fron != root->leftChild)
                s.push(fron);
            fron = fron->leftChild;
        }
        z += fron->data;
        if (fron->rTag != Thread && fron->rightChild != NULL)
        {
            fron = fron->rightChild;
            t = 0;
        }
        else if (!s.empty())
        {
            fron = s.top();
            t = 1;
            s.pop();
        }
    }
    z += fron->data;
    int i = 0;
    for(;i < z.length(); i++)
    {
        if (z[i] == u.data)
            break;
    }
    if (i != z.length())
        return locateNode(z[i + 1]);
    else
        return locateNode(z[0]);
}

class com
{
public:
    bool operator()(TreeNode* f, TreeNode* e) const
    {
        return f->data < e->data;
    }
};

HuffmanTree::HuffmanTree(const int& n, const int arr[])    
{
    num = n;
    root = new TreeNode('^', NULL, NULL, Link, Link);
    int pos[10000];
    multiset<TreeNode*, com> s;
    for (int i = 0; i < n; i++)
    {
        s.insert(new TreeNode(arr[i], NULL, NULL, Link, Link));
    }
    while (s.size() > 2)
    {
        TreeNode* t1 = *s.begin();
        s.erase(s.begin());
        TreeNode* t2 = *s.begin();
        s.erase(s.begin());
        s.insert(new TreeNode((t1->data + t2->data), t2, t1, Link, Link));
    }
    root->rightChild = *s.begin();
    s.erase(s.begin());
    root->leftChild = *s.begin();
}
HuffmanTree::~HuffmanTree()     
{
    queue<TreeNode*> s;
    s.push(root);
    stack<TreeNode*> del;
    del.push(root);
    TreeNode* fron = root;
    while (!s.empty())
    {
        if (fron->leftChild != NULL)
        {
            del.push(fron->leftChild);
            s.push(fron->leftChild);
            //fron->leftChild = NULL;
        }
        if (fron->rightChild != NULL)
        {
            del.push(fron->rightChild);
            s.push(fron->rightChild);
            //fron->rightChild = NULL;
        }
        if (!s.empty())
        {
            if (s.front() == root)
                s.pop();
            fron = s.front();
            s.pop();
        }
    }
    while (!del.empty())
    {
        delete del.top();
        del.pop();
    }
}

void HuffmanTree::printHuffmanCodes()
{
    TreeNode* fron = root;
    queue<TreeNode*> s;
    queue<string> d;
    string str;
    string test = "";

    string arr[10000];
    while (!s.empty() || !(fron->leftChild == NULL && fron->rightChild == NULL))
    {
        if (fron->leftChild == NULL && fron->rightChild == NULL)
        {
            cout << int(fron->data) << ":" << d.front() << endl;
            d.pop();
            s.pop();
        }
        if (fron->leftChild != NULL)
        {
            string te = "";
            if (!d.empty())
            {
                te = d.front();
                test = d.front();   
                d.pop();
                s.pop();
            }
            d.push(te + "1");
            s.push(fron->leftChild);
        }
        if (fron->rightChild != NULL)
        {
                d.push(test + "0");
                s.push(fron->rightChild);
        }
        if (!s.empty())
        {
                fron = s.front();
        }
    }
}
